2588. Symmetry
Farmer John loves
symmetry and is currently arranging his cows on his field partitioned into an n * m grid.
To preserve
symmetry, Farmer John places cows in the following way. He puts a cow in the
very center grid-square of the field; if no such grid-square exists, he simply
stops. Then he partitions the field into four equal-sized smaller fields
(separated by the row and column of the cow in the center) and arranges cows on
each of those fields as before. He repeats the partitioning for ever-smaller
fields until no center grid-square of a field exists or the field cannot be
subdivided.
By way of
example, if n = 7 and m = 15 then Farmer John will place a cow
in row 4, column 8 and arrange each of the resulting 3 * 7 fields. In each of
the 3 * 7 fields, Farmer John will place a cow in row 2, column 4 and arrange
each of the resulting 1 * 3 fields. The process is shown here
(where C denotes a cow):
21 cows are
required for this field. On the other hand, if n = m = 5 then Farmer
John will only need to place one cow since the resulting 2 * 2 fields do not have center grid-squares.
Help Farmer John determine how many cows he needs to arrange his field.
Input. Two integers n and m (1 ≤ n ≤ 109, 1
≤ m ≤ 109).
Output. Print the number
of cows needed.
|
Sample input |
Sample output |
|
7 15 |
21 |
SOLUTION
recursion
Algorithm analysis
Let f(n, m)
be the number of cows that can be placed on a field of size n * m.
If n or m is even, then the field has no center, so it is impossible to
place any cows on it. In this case f(n,
m) = 0.
If both n and m are odd, then place one cow in the center and then recursively
place the cows in four fields of size n
/ 2 * m / 2:
f(n, m)
= 1 + 4 * f(n / 2, m / 2)
Example
Find the answer
for the given test case.
f(7, 15) = 1 + 4
* f(3, 7) = 21
f(3, 7) = 1 + 4 * f(1, 3) = 5
f(1, 3) = 1 + 4 * f(0, 1) = 1
Algorithm realization
The function f returns the number of cows
that can be placed in the field of size n * m.
long long f(int n, int m)
{
if (n % 2
== 0 || m % 2 == 0) return 0;
return 1 +
4 * f(n / 2, m / 2);
}
The main part of the program. Read the input data. Compute and print
the answer.
scanf("%d %d",
&n, &m);
res = f(n, m);
printf("%lld\n",
res);
Java
realization
import java.util.*;
public class Main
{
static long f(int n, int m)
{
if (n % 2 ==
0 || m % 2 == 0) return 0;
return 1 + 4 * f(n/2, m/2);
}
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
int n = con.nextInt();
int m = con.nextInt();
long res = f(n, m);
System.out.println(res);
}
}
Python
realization
def f(n, m):
if n % 2 == 0 or m % 2 == 0: return 0
return 1 + 4 * f(n // 2, m // 2)
n, m = map(int,input().split())
res = f(n, m);
print(res)